package slidingwindows.leetcode.editor.cn;

/**
 * @Author: Dang Qi
 * @Question.Title: 滑动窗口中位数
 * @Question.No: 1208
 * @Date: 2021/2/5  10:04
 * @Description:
 */
public class GetEqualSubstringsWithinBudget {
    public static void main(String[] args) {
        Solution solution = new GetEqualSubstringsWithinBudget().new Solution();
        String s = "anryddgaqpjdw";
        String t = "zjhotgdlmadcf" ;
        int maxCost = 5;
        System.out.println(solution.equalSubstring(s,t,maxCost));
    }
    class Solution {
        public int equalSubstring(String s, String t, int maxCost) {
            int max = 0;
            int curCost = 0;
            int left = 0, right = 0;
            while(right < s.length()){
//                System.out.println("Test");
                int cost = getCost(right, s, t);
                if(cost + curCost <= maxCost){
                    curCost += cost;
                    right++;
                    max = max > right-left ? max : right-left;
                }else if(cost + curCost > maxCost){
                    curCost -= getCost(left, s, t);
                    left++;

                }
            }
            return max;
        }
        public int getCost(int i, String s, String t){
            int res = s.charAt(i) - t.charAt(i);
            return res >= 0 ? res : -res;
        }
    }
}
